package tp5;
import java.math.BigInteger;
import java.util.Vector;

class Generateur{
	BigInteger a;
	BigInteger p;
	Vector<BigInteger> listR;
	BigInteger getA(){
		return a;
	};
    
	BigInteger getP(){
		return p;
	};
	
	Generateur(int numBit){
		BigInteger deux = new BigInteger("2");
		BigInteger moinsUn = new BigInteger("-1");
		BigInteger moinsDeux = new BigInteger("-2");
		listR = new Vector<BigInteger>();
     
     //chercher p plus grand possible
     p = deux.pow(numBit).add(moinsUn); // commencer avec p = 2^n - 1
 
     while(true)
     {
    	 if((p.isProbablePrime(100))&&(p.add(moinsUn).divide(deux).isProbablePrime(100))){ // p et (p-1)/2 sont premier
    		 //chercher r
    		 BigInteger q = p.add(moinsUn).divide(deux);
    		 listR.add(q);   
    		 listR.add(deux);
    		 
//    		 System.out.println(listR.size() +  " " + listR);
             
             //chercher a
             a =new BigInteger("0");
             
             boolean isGenerateur;
             while(true){
	    	   a = a.add(BigInteger.ONE);
	    	   isGenerateur=true;
	    	   for(int i=0; i < listR.size(); i++){ // tester avec tous les r dans la liste
	    		 BigInteger r = (BigInteger) listR.elementAt(i);
	    		 //if (a^((p-1)/r) != 1)mod p
	    		 if(a.pow(p.add(moinsUn).divide(r).intValue()).mod(p).equals(BigInteger.ONE)){
	    			 isGenerateur=false;
	    			 break;
	    		 }
	    	   }
	    	   if(isGenerateur) break;
             }
             if(isGenerateur) break;
    	 }else
    		 p = p.add(moinsDeux); // decrementer p, p doit etre impair
     }
  }
 
  public static void main(String arg[]){
	  
	 int input = Integer.parseInt(arg[0]);
	 	  
	 Generateur e=new Generateur(input);
	 System.out.println("p = " + e.getP());
	 System.out.println("a = " + e.getA());
  }
}